package com.code;

/**
 * 描述:
 * 二分查找法
 *
 * @author luzhongfu
 * @create 2018-12-23 8:13 PM
 */
public class SortDichotomia {

    public static int sort_dichotomia(int[] data , int n , int traget){
        int l = 0 , r = n -1;
        //该区间为 [l , r]
        //若 l = 0 r = n 那么该区间为 [l , r)
        while( l <= r){
            int mid = (l+r)/2; //整形溢出可替换 l + (r-l)/2
            if(data[mid] == traget){
                return mid;
            }
            if(data[mid] > traget){
                r = mid - 1;
            }
            if(data[mid] < traget){
                l = mid + 1;
            }
        }
        return -1;
    }

    public static int sort_2(int[] data, int low, int high, int key){

        if(low <= high){
            int mid = low + ((high - low) >> 1);
            if(data[mid] == key){
                return mid;
            }else if (data[mid] > key){
                return sort_2(data,low, mid - 1,key);
            }else if (data[mid] < key){
                return sort_2(data,mid + 1,high, key);
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        int[] data = new int[1000];

        for ( int i = 0 ; i < 999 ; i++){
            data[i] = i;
        }
        int i = sort_2(data, 0,999, 300);
        System.out.println("找到了这个元素：位置是："+i);
    }

}
